#ifndef __Array_hpp__
#define __Array_hpp__

#include "Exception.hpp"

namespace ge {

//----------------------------------------------------------------------------//
// Array< T > 
//----------------------------------------------------------------------------//

template < class T >
class Array
{
 public:

     Array( void ) : m_data( 0 ), m_total( 0 ), m_used( 0 )
     {
     }

     Array( const Array< T >& _other ) : m_data( 0 ), m_total( 0 ), m_used( 0 )
     {
          if( !_other.IsEmpty() )
          {
              Reserve( _other.Count() );
              Append( _other.Data(), _other.Count() ); 
          }
     }

     explicit Array( const T* _e ) : m_data( 0 ), m_total( 0 ), m_used( 0 )
     {
          if( _e )
          {
               Reserve( 1 );
               Append( _e );
          }
     }

     explicit Array( const T& _e ) : m_data( 0 ), m_total( 0 ), m_used( 0 )
     {
          Reserve( 1 );
          Append( _e );
     }

     explicit Array( const T* _e, uint _count ) : m_data( 0 ), m_total( 0 ), m_used( 0 )
     {
          if( _e && _count )
          {
               Reserve( _count );
               Append( _e, _count );
          }
     }

     explicit Array( const T& _e, uint _count ) : m_data( 0 ), m_total( 0 ), m_used( 0 )
     {
          if( _count )
          {
               Reserve( _count );
               Append( _e, _count );
          }
     }

     ~Array( void )
     {
          Free();
     }

     Array& operator = ( const Array< T >& _other )
     {
          if( _other.Data() != m_data )
          {
               if( _other.IsEmpty() )
               {
                    Clear();
               }
               else
               {
                    Reserve( _other.Count() );
                    Append( _other.Data(), _other.Count() );
               }
          }

          return *this;
     }

     Array& operator = ( const T& _e )
     {
          Clear();
          Reserve( 1 );
          Append( _e );

          return *this;
     }

     Array& operator += ( const Array< T >& _other )
     {
          if( !_other.IsEmpty() ) Append( _other.Data(), _other.Count() );

          return *this;
     }

     Array& operator += ( const T& _e )
     {
          Append( _e );

          return *this;
     }

     Array operator + ( const Array< T >& _other ) const
     {
          Array _sum( *this );

          if( !_other.IsEmpty() )
          {
               _sum.Reserve( _other.Count() );
               _sum.Append( _other.Data(), _other.Count() );
          }
     
          return _sum;
     }

     Array operator + ( const T& _e ) const
     {
          Array _sum( *this );
          _sum.Reserve( 1 );
          _sum.Append( _e );

          return _sum;
     }

     friend Array operator + ( const T& _e, const Array& _array )
     {
          return Array( _e ) + _array;
     }

     bool operator < ( const Array< T >& _other ) const
     {
          if( m_data != _other.m_data )
          for( register uint i = 0, _max = Min( m_used, _other.Count() ); i < _max; ++ i )
          {
               if( !( m_data[ i ] < _other[ i ] ) ) return false;
          }

          return m_used < _other.Count();
     }

     bool operator <= ( const Array< T >& _other ) const
     {
          if( m_data != _other.m_data )
          for( register uint i = 0, _max = Min( m_used, _other.Count() ); i < _max; ++ i )
          {
               if( !( m_data[ i ] <= _other[ i ] ) ) return false;
          }

          return m_used <= _other.Count();
     }

     bool operator == ( const Array< T >& _other ) const
     {
          if( m_data != _other.m_data )
          for( register uint i = 0, _max = Min( m_used, _other.Count() ); i < _max; ++ i )
          {
               if( !( m_data[ i ] == _other[ i ] ) ) return false;
          }

          return m_used == _other.Count();
     }

     bool operator != ( const Array< T >& _other ) const
     {
          return !( (*this) == _other );
     }

     bool operator > ( const Array< T >& _other ) const
     {
          return !( (*this) <= _other );
     }

     bool operator >= ( const Array< T >& _other ) const
     {
          return !( (*this) < _other );
     }

     bool IsEmpty( void ) const
     {
          return m_used == 0;
     }

     bool NonEmpty( void ) const
     {
          return m_used != 0;
     }

     uint Count( void ) const
     {
          return m_used;
     }

     uint Size( void ) const
     {
          return m_used;
     }

     uint Unused( void ) const
     {
          return m_total - m_used;
     }

     uint Total( void ) const
     {
          return m_total;
     }

     T* Data( void )
     {
          return m_data;
     }

     const T* Data( void ) const
     {
          return m_data;
     }

     T* Data( uint _at )
     {
          geDebugAssertT( FailedAccess, _at < m_used, "Array< T > - Invalid index (index = %d, size = %d)", _at, m_used );
          return m_data + _at;
     }

     const T* Data( uint _at ) const
     {
          geDebugAssertT( FailedAccess, _index < m_used, "Array< T > - Invalid index (index = %d, size = %d)", _at, m_used );
          return m_data + _at;
     }

     T& operator [] ( uint _index )
     {
          geDebugAssertT( FailedAccess, _index < m_used, "Array< T > - Invalid index (index = %d, size = %d)", _index, m_used );
          return m_data[_index];
     }

     const T& operator [] ( uint _index ) const
     {
          geDebugAssertT( FailedAccess, _index < m_used, "Array< T > - Invalid index (index = %d, size = %d)", _index, m_used );
          return m_data[_index];
     }

     T& At( uint _index )
     {
          geDebugAssertT( FailedAccess, _index < m_used, "Array< T > - Invalid index (index = %d, size = %d)", _index, m_used );
          return m_data[_index];
     }

     const T& At( uint _index ) const
     {
          geDebugAssertT( FailedAccess, _index < m_used, "Array< T > - Invalid index (index = %d, size = %d)", _index, m_used );
          return m_data[_index];
     }

     T& Last( void )
     {
          geDebugAssertT( FailedAccess, m_used > 0, "Array< T > - No last element" );
          return m_data[m_used-1];
     }

     const T& Last( void ) const
     {
          geDebugAssertT( FailedAccess, m_used > 0, "Array< T > - No last element" );
          return m_data[m_used-1];
     }

     T& First( void )
     {
          geDebugAssertT( FailedAccess, m_used > 0, "Array< T > - No first element" );
          return m_data[0];
     }

     const T& First( void ) const
     {
          geDebugAssertT( FailedAccess, m_used > 0, "Array< T > - No first element" );
          return m_data[0];
     }

     T& Top( void )
     {
          geDebugAssertT( FailedAccess, m_used > 0, "Array< T > - No top element" );
          return m_data[m_used-1];
     }

     const T& Top( void ) const
     {
          geDebugAssertT( FailedAccess, m_used > 0, "Array< T > - No top element" );
          return m_data[m_used-1];
     }

     void Push( const T& _value )
     {
          Append( _value );
     }

     void Pop( void )
     {
          RemoveLast();
     }

     void Pop( uint _count )
     {
          RemoveLast( _count );
     }

     void Resize( uint _count, const T& _sample = T() )
     {
          if( m_used < _count ) Append( _sample, _count - m_used ); 
          else if( m_used != _count ) RemoveLast( m_used - _count );
     }

     void Reserve( uint _count )
     {
          if( m_total < m_used + _count )
          {
               T* _tmp = _Allocate( _count );
               if( _tmp )
               {
                    if( m_used )
                    {
                         _Construct( _tmp, m_data, m_used );
                         _Destruct( m_data, m_used );
                    }

                    if( m_data )_Deallocate( m_data );

                    m_data = _tmp;
                    m_total = _count;
               }
          }
     }

     void Free( void )
     {
           if( m_data )
           {
                if( m_used ) _Destruct( m_data, m_used );

                _Deallocate( m_data );

                m_data = 0;
                m_total = 0;
                m_used = 0;
           }
     }

     void Clear( void )
     {
          if( m_used )
          {
               _Destruct( m_data, m_used );
               m_used = 0;
          }
     }

     void Pack( uint _max_unused = 0 )
     {
          if( m_total - m_used > _max_unused )
          {
               if( m_used )
               {
                    T* _tmp = _Allocate( m_used );
                    if( !_tmp ) return; // not enough of memory

                    _Construct( _tmp, m_data, m_used );
                    _Destruct( m_data, m_used );
                    _Deallocate( m_data );
                    m_data = _tmp;
                    m_total = m_used;
               }
               else
               {
                    Free();
               }
          }
     }

     uint SearchByAddress( const T& _e ) const
     {
          return SearchByAddress( &_e );
     }

     uint SearchByAddress( const T* _e ) const  
     {
          if( _e < m_data || _e > m_data + m_used ) return ((uint)-1);

          uint _index = _e - m_data;

          if( _index >= m_used ) return ((uint)-1);

          return _index;
     }

     template < class C >
     uint Search( const T& _value, const C& _cmp = C() ) const
     {
          for( uint i = 0; i < m_used; ++ i )
          {
               if( _cmp.Eq( m_data[i], _value ) ) return i;
          }

          return ((uint)-1);
     }

     uint Search( const T& _value ) const
     {
          return Search( _value, Less< T >() );
     }

     template < class C >
     uint ReverseSearch( const T& _value, const C& _cmp = C() ) const
     {
          for( uint i = m_used; i > 0;  )
          {
               if( _cmp.Eq( m_data[--i], _value ) ) return i;
          }

          return ((uint)-1);
     }

     uint ReverseSearch( const T& _value ) const
     {
          return ReverseSearch( _value, Less< T >() );
     }

     template < class C >
     uint BinarySearch( const T& _key, const C& _cmp = C() ) const
     {
          if( m_used > 0 )
          for( uint _l = 0, _r = m_used-1, _c; _l <= _r; )
          {
               _c = (_l+_r) >> 1;
               if( !_cmp.Le( _key, m_data[_c] ) ) _l = _c + 1;
               else if( !_cmp.Le( _key, m_data[_c] ) ) _r = _c - 1; 
               else return _c;
          }

          return ((uint)-1);
     }

     uint BinarySearch( const T& _value ) const
     {
          return BinarySearch( _value, Less< T >() );
     }

     template < class C >
     uint SearchNext( uint _origin, const T& _value, const C& _cmp = C() ) const
     {
          if( _origin < m_used )
          for( uint i = ++ _origin; i < m_used; ++ i )
          {
               if( _cmp.Eq( m_data[ i ], _value ) ) return i;
          }

          return m_used;
     }

     uint SearchNext( uint _origin, const T& _value ) const
     {
          return SearchNext( _origin, _value, Less< T >() );
     }

     template < class C >
     uint ReverseSearchNext( uint _origin, const T& _value, const C& _cmp = C() ) const
     {
          if( _origin > 0 )
          for( uint i = _origin; i > 0 && i <= m_used; )
          {                                   
               if( _cmp.Eq( m_data[ --i ], _value ) == 0 ) return i;
          }

          return (uint)-1;
     }

     uint ReverseSearchNext( uint _origin, const T& _value ) const
     {
          return ReverseSearchNext( _origin, _value, Less< T >() );
     }

     template < class C >
     uint SearchLast( const T& _value, const C& _cmp = C() ) const
     {
          return ReverseSearch( _value, _cmp );
     }

     uint SearchLast( const T& _value ) const
     {
          return ReverseSearch( _value, Less< T >() );
     }

     template < class C >
     uint ReverseSearchLast( const T& _value, const C& _cmp = C() ) const
     {
          return Search( _value, _cmp );
     }

     uint ReverseSearchLast( const T& _value ) const
     {
          return Search( _value, Less< T >() );
     }

     void Reverse( uint _start = 0, uint _count = (uint)-1 )
     {
          register T* _l = m_data + _start;
          register T* _r = m_data + geChoose( _count > m_used, m_used, _count );
          register T* _e = m_data + m_used;

          while( _l < _e && _r <= _e && _l < _r )
          {
               -- _r;
               if( _l != _r ) Swap( *_l, *_r );
               ++ _l;
          }
     }

     template< class C, class S >
     void Sort( uint _start, uint _count, const C& _cmp = C(), const S& _sorter = S() )
     {
          if( _start < m_used )
          {
               if( _count > m_used ) _count = m_used;
               _count = m_used - _start;
               if( _count ) _sorter.Sort( m_data + _start, _count, _cmp ); 
          }
     }

     template< class C, class S >
     void Sort( const C& _cmp = C(), const S& _sorter = S() )
     {
          Sort( 0, m_used, _cmp, _sorter );
     }

     template< class C >
     void Sort( const C& _cmp = C() )
     {
          Sort( 0, m_used, _cmp, QuickSort< T >() );
     }

     template< class C >
     void Sort( uint _start, uint _count, const C& _cmp = C() )
     {
          Sort( _start, _count, _cmp, QuickSort< T >() );
     }

     void Sort( uint _start, uint _count )
     {
          Sort( _start, _count, Less< T >(), QuickSort< T >() );
     }

     void Sort( void )
     {
          Sort( Less< T >(), QuickSort< T >() );
     }

     void InvertedSort( uint _start, uint _count )
     {           
          Sort( _start, _count, Greater< T >(), QuickSort< T >() );
     }

     void InvertedSort( void )
     {
          Sort( 0, m_used, Greater< T >(), QuickSort< T >() );
     }

     void Append( const T& _e )
     {
          if( m_used == m_total )
          {
               // guard
               if( SearchByAddress( &_e ) < m_used )
               {
                    T* _tmp = _Allocate( 1 );
                    _Construct( _tmp, _e );
                    Append( *_tmp ); // insertInEnd copy
                    _Destruct( _tmp );
                    _Deallocate( _tmp );
                    return;
               }

               if( !_Upsize( 1 ) ) return; // not enough of memory
          }

          _Construct( m_data + m_used, _e );
          ++ m_used;
     }

     void Append( const T* _e )
     {
          if( _e ) Append( *_e ); 
     }

     void Append( const T& _e, uint _count )
     {
          if( _count )
          {
               if( ( m_total - m_used ) < _count )
               {
                    // guard
                    if( SearchByAddress( &_e ) < m_used )
                    {
                         T* _tmp = _Allocate( 1 );
                         _Construct( _tmp, _e );
                         Append( *_tmp, _count ); // insertInEnd copy
                         _Destruct( _tmp );
                         _Deallocate( _tmp );
                         return;
                    }

                    if( !_Upsize( _count ) ) return; // not enough of memory
               }

               _Construct( m_data + m_used, _e, _count );
               m_used += _count;
          }
     }

     void Append( const T* _e, uint _count )
     {
          if( _e && _count )
          {
               if( ( m_total - m_used ) < _count )
               {
                    // guard
                    if( SearchByAddress( _e ) < m_used )
                    {
                         T* _tmp = _Allocate( _count );
                         _Construct( _tmp, _e, _count );
                         Append( _tmp, _count ); // insertInEnd copy
                         _Destruct( _tmp, _count );
                         _Deallocate( _tmp );
                         return;
                    }

                    if( !_Upsize( _count ) ) return; // not enough of memory
               }

               _Construct( m_data + m_used, _e, _count );
               m_used += _count;
          }
     }

     void Insert( const T& _e, uint _at )
     {
          if( _at == m_used )
          {
               Append( _e );
          }
          else if( _at < m_used )
          {
               // guard
               if( SearchByAddress( &_e ) < m_used )
               {
                    T* _tmp = _Allocate( 1 );
                    _Construct( _tmp, _e );
                    Insert( *_tmp, _at ); // insertInEnd copy
                    _Destruct( _tmp );
                    _Deallocate( _tmp );
                    return;
               }

               if( m_used == m_total )
               {
                    if( !_Upsize( 1, _at ) ) return; // not enough of memory

                    _Construct( m_data + _at, _e );
               }
               else
               {
                    register T* _iter = m_data + ( m_used - 1 );
                    register T* _end = m_data + _at;

                    _Construct( m_data + m_used, *_iter );

                    while( _iter > _end )
                    {
                         _iter[ 0 ] = _iter[ -1 ];
                         -- _iter;
                    }

                    m_data[ _at ] = _e;
               }

               ++ m_used;
          }
     }

     void Insert( const T* _e, uint _at )
     {
          if( _e ) Insert( *_e, _at );
     }

     void Insert( const T& _e, uint _at, uint _count ) // !!! Not tested !!!
     {
          if( !_e || !_count )
          {
               return;
          }

          if( _at == m_used )
          {
               Append( _e, _count );
          }
          else if( _at < m_used )
          {
               // guard
               if( SearchByAddress( &_e ) < m_used )
               {
                    T* _tmp = _Allocate( 1 );
                    _Construct( _tmp, _e );
                    Insert( _tmp, _at, _count ); // insertInEnd copy
                    _Destruct( _tmp );
                    _Deallocate( _tmp );
                    return;
               }

               if( ( m_total - m_used ) < _count )
               {
                    if( !_Upsize( _count, _at ) ) return; // not enough of memory

                    _Construct( m_data + _at, _e, _count );
               }
               else
               {
                    register const T* _srcp = m_data + m_used;
                    register T* _dstp =  m_data + m_used + _count;
                    register const T* _endp = m_data + m_used;
                    register const T* _endd = m_data + _at;

                    while( _srcp > _endd && _dstp > _endp )
                    {
                         -- _srcp;
                         -- _dstp;

                         _Construct( _dstp, *_srcp );
                    }
                    
                    _dstp = m_data + m_used;
                    _srcp = _dstp - _count;
                    _endp = m_data + _at;

                    while( _srcp > _endp )
                    {
                         -- _srcp;
                         -- _dstp;
                         *_dstp = *_srcp;
                    }

                    for( _dstp = m_data + _at, _endp =  m_data + _at + _count; _dstp < _endp ; ++ _dstp )
                    {
                         *_dstp = _e;
                    }
               }

               m_used += _count;
          }
     }

     void Insert( const T* _e, uint _at, uint _count )
     {
          if( !_e || !_count )
          {
               return;
          }

          if( _at == m_used )
          {
               Append( _e, _count );
          }
          else if( _at < m_used )
          {
               // guard
               if( SearchByAddress( _e ) < m_used )
               {
                    X* _tmp = _Allocate( _count );
                    _Construct( _tmp, _e, _count );
                    Insert( _tmp, _at, _count ); // insertInEnd copy
                    _Destruct( _tmp, _count );
                    _Deallocate( _tmp );
                    return;
               }

               if( ( m_total - m_used ) < _count )
               {
                    if( !_Upsize( _count, _at ) )  return; // not enough of memory

                    _Construct( m_data + _at, _e, _count );
               }
               else
               {
                    register const T* _srcp = m_data + m_used;
                    register T* _dstp =  m_data + m_used + _count;
                    register const T* _endp = m_data + m_used;
                    register const T* _endd = m_data + _at;

                    while( _srcp > _endd && _dstp > _endp )
                    {
                         -- _srcp;
                         -- _dstp;

                         _Construct( _dstp, *_srcp );
                    }
                    
                    _dstp = m_data + m_used;
                    _srcp = _dstp - _count;
                    _endp = m_data + _at;

                    while( _srcp > _endp )
                    {
                         -- _srcp;
                         -- _dstp;
                         *_dstp = *_srcp;
                    }

                    for( _srcp = _e, _dstp = m_data + _at, _endp = _e + _count; _srcp < _endp ; ++ _srcp, ++ _dstp )
                    {
                         *_dstp = *_srcp;
                    }
               }

               m_used += _count;
          }
     }

     bool RemoveLast( void )
     {
          if( m_used )
          {
               _Destruct( m_data + ( m_used - 1 ) );
               -- m_used;
               return true;
          }

          return false;
     }

     bool RemoveLast( uint _count )
     {
          if( _count > m_used ) _count = m_used;
         
          if( _count )
          {
               _Destruct( m_data + ( m_used - _count ), _count );
               m_used -= _count;
               return true;
          }

          return false;
     }

     bool Remove( uint _from )
     {
          if( _from >= m_used )
          {
              return false;
          }

          register T* _srcp = m_data + _from + 1;
          register T* _dstp = m_data + _from;
          register T* _endp = m_data + m_used;

          for( ; _srcp < _endp; ++ _srcp, ++ _dstp )
          {
               *_dstp = *_srcp;
          }

          _Destruct( _srcp );

          -- m_used;

          return true;
     }

     bool Remove( uint _from, uint _count )
     {
          uint _end = _from + _count;
          
          if( ( _from + _count ) > m_used )
          {
               _count = m_used - _from;
               _end = m_used;
          }

          if( !_count || _from >= m_used ) return false;

          register T* _srcp = m_data + _end;
          register T* _dstp = m_data + _from;
          register T* _endp = m_data + m_used;

          for( ; _srcp < _endp; ++ _srcp, ++ _dstp )
          {
               *_dstp = *_srcp;
          }

          _Destruct( _srcp, _count );

          m_used -= _count;

          return true;
     }

     void FastRemove( uint _index )
     {
          if( _index < m_used )
          {
               m_data[_index] = m_data[m_used-1];
               RemoveLast();
          }
     }
     
     void Swap( Array& _array )
     {
          ge::Swap( m_data, _array.m_data );
          ge::Swap( m_total, _array.m_total );
          ge::Swap( m_used, _array.m_used );
     }

 protected:

     bool _Upsize( uint _up )
     {
          uint _new_used = m_used + _up;
          uint _new_total = ( _new_used ) + 10 + ( _new_used >> 1 ) + ( _new_used >> 4 ); 

          T* _new_data = _Allocate( _new_total );

          if( _new_data )
          {
               if( m_data )
               {
                    for( register uint i = 0; i < m_used; ++ i )
                    {
                         _Construct( _new_data + i, m_data[ i ] );
                         _Destruct( m_data + i );
                    }

                    _Deallocate( m_data );
               }

               m_data = _new_data;
               m_total = _new_total;

               return true;
          }
               
          return false;
     }

     bool _Upsize( uint _up, uint _at )
     {
          uint _new_used = m_used + _up;
          uint _new_total = ( _new_used ) + 10 + ( _new_used >> 1 ) + ( _new_used >> 4 );

          T* _new_data = _Allocate( _new_total );

          if( _new_data )
          {
               if( m_data )
               {
                    T* _srcp = m_data;
                    T* _dstp = _new_data;

                    if( _at ) // before insert
                    {
                         _Construct( _dstp, _srcp, _at );
                         _srcp += _at;
                         _dstp += _at;
                    }

                    if( m_used - _at ) // after insert
                    {
                         _dstp += _up;
                         _Construct( _dstp, _srcp, m_used - _at );
                    }

                    _Destruct( m_data, m_used );
                    _Deallocate( m_data );
               }

               m_data = _new_data;
               m_total = _new_total;

               return true;
          }
               
          return false;
     }

     static void _Destruct( register T* _e, register uint _count )
     {
          assert( _e != 0 && _count > 0 );
          while( _count -- )
          {
               _e -> ~T();
               ++ _e;
          }
     }

     static void _Construct( register T* _e, const T& _s, register uint _count )
     {
          assert( _e != 0 && _count > 0 );

          while( _count -- )
          {
               ::new( reinterpret_cast< void* >( _e ) ) T( _s );
               ++ _e;
          }
     }

     static void _Construct( register T* _e, register const T* _s, register uint _count )
     {
          assert( _e != 0 && _s != 0 && _count > 0 );

          while( _count -- )
          {
               ::new( reinterpret_cast< void* >( _e ) ) T( *_s );
               ++ _e;
               ++ _s;
          }
     }

     static T* _Allocate( uint _count )
     {
          assert( _count > 0 );
          return (T*)new uint8[ _count * sizeof( T ) ];
     }

     static void _Construct( T* _e, const T& _s )
     {
          assert( _e != 0 );
          ::new( reinterpret_cast< void* >( _e ) ) T( _s );
     }

     static void _Destruct( T* _e )
     {
          assert( _e != 0 );
          _e -> ~T();
     }

     static void _Deallocate( T* _m )
     {
          assert( _m != 0 );
          delete [] ((uint8*)_m);
     }

     T* m_data;
     uint m_total;
     uint m_used;
};

template < class T >
void Swap( typename Array< T >& _a, typename Array< T >& _b )
{
     _a.Swap( _b );
}

} // namespace ge

#endif//__Array_hpp__
